package oj.oj_niuke_构建二叉树;

// 连导包也得自己处理
import java.util.*;
import java.io.*;

// 定义二叉树结点类
// 一个文件中只能有一个 public 类
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return String.format("%c", val);
    }
}

// 类名必须叫做 Main
public class Main {
    // 自己动手写 main 方法
    public static void main(String[] args) {
        // 自己动手读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取一行，读取到 String 中
        String preorder = scanner.nextLine();
        // 利用这行前序序列，构建二叉树出来
        // 二叉树的结点类也需要我们自己定义

        // 为了方便处理，把 String -> List<Character>
        List<Character> preorderList = toList(preorder);

        // 构建二叉树
        TreeNode root = buildTree(preorderList);

        // 要求进行中序遍历，严格按照题目的要求进行输出
        inorderTraversal(root);
    }

    // 由于要在 main 方法（静态方法）中调用，我们的方法得是静态方法
    private static List<Character> toList(String s) {
        // 后边要头删 remove(0)，所以 LinkedList O(1) 比 ArrayList O(n) 好
        List<Character> list = new LinkedList<>();
        for (char c : s.toCharArray()) {
            list.add(c);
        }
        return list;
    }

    private static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        inorderTraversal(root.left);
        // 进行根的值的输出，要符合格式
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    private static TreeNode buildTree(List<Character> preorder) {
        if (preorder.size() == 0) {
            return null;
        }

        // 头删的方式，取出根的值，删完之后，preorder 中的元素少了一个
        char rootVal = preorder.remove(0);
        if (rootVal == '#') {
            // # 代表空树
            return null;
        }

        TreeNode root = new TreeNode(rootVal);

        // 构建左子树，由于 remove(0) 头删，已经删除了第一个结点了，所以，这里的 preorder 就没有了第一个元素
        root.left = buildTree(preorder);    // 看起来还是 preorder，但已经少了一个了
        // 注意：在构建左子树的过程中，preorder 中的元素一直在减少，所以，还是叫做 preorder，其中的元素已经没多少了
        // 此刻 preorder 就剩用来构建右子树中的序列了
        root.right = buildTree(preorder);   // 看起来还是 preorder，但已经少了很多了（我们也不知道少了多少个）

        // 返回树的根
        return root;
    }
}

